package leetcode.code1792;

import java.util.PriorityQueue;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution2 implements IDebug {
	public double maxAverageRatio(int[][] classes, int extraStudents) {
		int num = classes.length;
		PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> {
			if (((a[0] + 1) / (a[1] + 1) - (b[0] + 1) / (b[1] + 1) - a[0] / a[1] + b[0] / b[1]) >= 0) {
				return -1;
			} else
				return 1;
		});
		for (int[] Class : classes) {
			pq.add(new double[] { Class[0], Class[1] });
		}
		while (extraStudents > 0) {
			double[] Class = pq.poll();
			pq.add(new double[] { Class[0] + 1, Class[1] + 1 });
			extraStudents--;
		}
		double ans = 0.0;
		while (!pq.isEmpty()) {
			double[] Class = pq.poll();
			ans += Class[0] / Class[1];
		}
		return ans / num;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(0.78333, this.maxAverageRatio(HelpDebug.str2array1("[[1,2],[3,5],[2,2]]"), 2));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(0.53485, this.maxAverageRatio(HelpDebug.str2array1("[[2,4],[3,9],[4,5],[2,10]]"), 4));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();

	}

}
